#include <limits.h>
#include <assert.h>
#include <stdlib.h>
#include <stdio.h>

#include "glib/glist.h"
#include "auxiliar_network/auxiliar_network.h"
#include "dinic_dfs.h"

#define INF ((UINT_MAX-1)/2);

#define label(gl) (nodeANet_getLabel(node(gl)))
#define node(gl) ((nodeANet) edge_getNeighbor(g_list_data(gl)))
#define edge(gl) ((edgeANet) g_list_data(gl))

#define print_flow(...) if(showflow) printf(__VA_ARGS__)
#define print_verb(...) if(showverb) printf(__VA_ARGS__)
#define print_mincut(...) if(showcut) printf(__VA_ARGS__)

/* Prototipos de funciones auxiliares */
static void dinic_blocking_step(auxNet net, const nodeANet s,
                        const nodeANet t, unsigned int *flow, unsigned int i);
static void move_on(auxNet net, GList **path, GList **cur_node);
static void go_back(auxNet net, GList **path, GList **cur_node);
static int get_min_residual_capacity(GList *path);
static void increase_flow(GList *path, unsigned int *flow);
static void update_flow(GList *path, unsigned int min_cap);

/* Variables externas creadas para prints de las opciones */
extern bool showflow;
extern bool showverb;
extern bool showcut;


void dinic(network n, const unsigned int s, const unsigned int t){
    auxNet an = NULL;
    nodeANet node_s = NULL, node_t = NULL;
    unsigned int flow = 0, i = 0;

    assert(n != NULL);

    while(true){
        i++;

        an = auxNetwork_create(n, s, t);
        if(an == NULL){
            /* No se encontró el nodo 's' en el network original... */
            printf("No se encontró el nodo 's'\n");
            return;
        }

        print_verb("\nN.A. %u:\n", i);

        /* Busco 's' y 't' */
        node_s = auxNetwork_getNode(an, s);
        node_t = auxNet_getSinkNode(an);

        /* Si 't' no está en el network auxiliar, termina. */
        if(node_t == NULL){
            print_verb("El N.A. %u aumenta el flujo en 0.\n", i);

            print_flow("\nFlujo Maximal:\n");
            if(showflow) network_printFlow(n);
            print_flow("\n");
            printf("Valor del flujo: %u\n",flow);

            print_mincut("Corte: ");
            if(showcut) auxNetwork_printNodes(an, s);

            an = auxNetwork_destroy(an);
            break;
        }

        /* Sino corro el paso bloqueante de Dinic */
        dinic_blocking_step(an, node_s, node_t, &flow, i);

        an = auxNetwork_destroy(an);
    }
    /* FIN */
}


static void dinic_blocking_step(auxNet net, const nodeANet s,
                        const nodeANet t, unsigned int *flow, unsigned int i){
    bool stop = false;
    GList *path = NULL, *neighbors = NULL, *gs = NULL;
    GList *cur_glist_node = NULL;
    edge edge_s = NULL;
    edgeANet edgeANet_s = NULL;
    unsigned int orig_flow = *flow;
    assert(net != NULL);

    /* EFICIENCIA */
    /* ARISTAS ficticia, para guardar a 's' en ellas */
    edge_s = edge_create(nodeANet_getNode(s),0);
    edgeANet_s = edgeANet_create(edge_s, s, true);
    /* NODO GLIST ficticio, para guardar la arista ficticia */
    gs = g_list_prepend(gs, edgeANet_s);

    /* Bucle externo. Termina cuando se ha demostrado que no hay ningún
     * camino desde 's' hacia 't'. */
    while(!stop){
        assert(g_list_length(path) == 0);

        /* Inicializar */
        path = g_list_prepend(path, gs);
        cur_glist_node = gs;

        /* Bucle interno. Termina cuando se encuentra un camino a 't',
         * o cuando se demuestra que no existe. */
        while((node(cur_glist_node) != t) && !stop){
            neighbors = nodeANet_getNeighbors(node(cur_glist_node));

            /* Si tengo vecinos en el nivel siguiente, avanzo. */
            if(g_list_length(neighbors) > 0){
                move_on(net, &path, &cur_glist_node);

            /* Si no hay vecinos, pero no estoy sobre 's',
             * vuelvo en busca de otro camino. */
            }else if(node(cur_glist_node) != s){
                go_back(net, &path, &cur_glist_node);

            /* Estoy sobre 's' pero no puedo avanzar: no hay camino. */
            }else{
                stop = true;
            }
        }
        /* Aumento flujo? */
        if(node(cur_glist_node) == t){
            /* se revierte la lista que se creo dada vuelta */
            path = g_list_reverse(path);
            increase_flow(path, flow);
        }
        g_list_free(path);
        path = NULL;
    }
    print_verb("El N.A. %u aumenta el flujo en %u.\n", i, *flow - orig_flow);

    g_list_free(path);
    edge_destroy(edge_s);
    edgeANet_destroy(edgeANet_s);
    g_list_free(gs);

    return;
}

static void move_on(auxNet net, GList **path, GList **cur_glist_node){
    GList *neighbors = NULL;

    assert(net != NULL);
    assert(*path != NULL);
    assert(*cur_glist_node != NULL);

    /* Obtengo un nodo de los vecinos de cur_node en el nivel superior. */
    neighbors = nodeANet_getNeighbors( node(*cur_glist_node) );
    assert(g_list_length(neighbors) > 0);

    *cur_glist_node = g_list_first(neighbors);

    /* Agrego nodo al camino.  Eficiencia: lista dada vuelta. */
    *path = g_list_prepend(*path, *cur_glist_node);
}

static void go_back(auxNet net, GList **path, GList **cur_glist_node){
    GList *prev_node = NULL;

    assert(net != NULL);
    assert(*path != NULL);

    /* Obtengo nodo padre y lo elimino del camino. */
    assert(node(g_list_data(g_list_first(*path))) == node(*cur_glist_node));

    prev_node = g_list_data(g_list_next(g_list_first(*path)));
    assert(prev_node != NULL);

    *path = g_list_remove(*path, *cur_glist_node);

    /* Elimino lado de net. O(1) pues trabajo con punteros a nodos de GList */
    nodeANet_setNeighbors(node(prev_node),
               g_list_delete_link(nodeANet_getNeighbors(
                            node(prev_node)), *cur_glist_node));

    *cur_glist_node = prev_node;
}

static void increase_flow(GList *path, unsigned int *flow){
    unsigned int min_cap = 0;

    assert(path != NULL);
    assert(g_list_length(path) > 0);

    min_cap = get_min_residual_capacity(path);

    if(min_cap > 0){
        *flow = *flow + min_cap;
        update_flow(path, min_cap);
        print_verb(" (flujo transportado: %u)\n", min_cap);
    }
}


static int get_min_residual_capacity(GList *path) {
    unsigned int min_cap = 0;
    unsigned int res_cap = 0;
    int flow = 0;
    GList *l1 = NULL, *l2 = NULL;
    nodeANet x = NULL;
    edgeANet e = NULL;

    min_cap = INF;

    /* Busco mínima capacidad residual. */
    l2 = g_list_first(path);
    assert(l2 != NULL);

    while(g_list_next(l2) != NULL){
        /* Obtengo una arista del camino. */
        l1 = l2;
        l2 = g_list_next(l1);
        x = node(g_list_data(l1));

        e = edge(g_list_data(l2));

        /* Calculo la capacidad residual. */
        res_cap = edgeANet_getCap(e);
        flow = edgeANet_getFlow(e);
        if(edgeANet_isForwardInNetwork(e)){
            res_cap = res_cap - flow;
        }else{
            res_cap = res_cap + flow;
        }

        /* Si la capacidad es 0 la arista se borra y se retorna 0
         * pues no va a haber una menor */
        if(res_cap == 0){
            nodeANet_delNeighbor(x, e);
            return 0;
        }
        /* Si la capacidad de esta arista es menor a la que se viene 
         * calculando, la actualizo. */
        if(res_cap < min_cap) min_cap = res_cap;

    }
    return min_cap;
}

static void update_flow(GList *path, unsigned int min_cap){
    GList *l1 = NULL, *l2 = NULL;
    edgeANet e = NULL, f = NULL;
    nodeANet x = NULL, y = NULL;
    
    /* Recorrer el path y actualizar el flujo */
    l2 = g_list_first(path);
    assert(l2 != NULL);

    print_verb("0 ");

    while(g_list_next(l2) != NULL){
        /* Obtengo una arista del camino. */
        l1 = l2;
        l2 = g_list_next(l1);

        x = node(g_list_data(l1));  /* nodo origen */
        y = node(g_list_data(l2));  /* nodoe destino */

        e = edge(g_list_data(l2));  /* arista actual */
        f = edge(g_list_data(l1));  /* arista anterior */

        /* Si es forward aumento el flujo a esa arista. */
        if(edgeANet_isForwardInNetwork(e)){
            print_verb("%u ",nodeANet_getLabel(y));
            edgeANet_increaseFlow(e, min_cap);
            node_addBackwardNeighbor(nodeANet_getNode(y), nodeANet_getNode(x),
                                     min_cap, edgeANet_getCap(e));

        /* En cambio si es backward decremento el flujo de esa arista. */
        }else{
            print_verb("<- %u ",nodeANet_getLabel(y));
            edgeANet_decreaseFlow(e, min_cap);

            /* Si la arista se vacio se borra de los vecinos backwards de y */
            if(edgeANet_getFlow(e) == 0){
                /* se usan los nodos internos a los nodeANet */
                node_delBackwardNeighbor(nodeANet_getNode(y),
                                         nodeANet_getNode(x));
            }
        }

        /* Si el flujo de la arista "anterior" es igual a su capacidad,
         * quito la arista del network auxiliar. */
        if(edgeANet_getFlow(f) == edgeANet_getCap(f)){
            nodeANet_delNeighbor(x, f);
        }
    }
}
